Real Numbers are Uncountable

Theorem

The set real numbers \(\mathbb{R}\) is uncountable.

Proof

This follows from cantor's diagonal argument applied to the sequences of digits of the decimal expansion of each real number.

That is, we consider any listing of the numbers in \([0, 1)\):

\[\begin{align*} 0 &\mapsto 0.\underline{2}349807123\dots \\ 1 &\mapsto 0.7\underline{1}02394803\dots \\ 2 &\mapsto 0.56\underline{3}2848834\dots \\ 3 &\mapsto 0.002\underline{3}029699\dots \\ 4 &\mapsto 0.0023\underline{0}29699\dots \\ \end{align*}\]

and take digits diagonally from the top left moving down and to the right to construct a new number in this interval

\[ 0.21330\dots.\]

We then construct a decimal expansion such that the value at each place differs from the above. In particular, each digit of our number will be \(1\) if it is not \(1\) in the original number, and \(2\) if it is \(1\). In our case we have

\[ 0.12111\dots\]

This number then does not appear in the listing.

Note that we choose which digits to use in each case to carefully avoid the problem of non-unique decimal expansions. In particular we avoid choosing \(0\) and \(9\), see characterisation of non-unique base b expansions.

Then we can trivially inject \([0, 1) \to \mathbb{R}\) to show that \(\mathbb{R}\) is also uncountable.